Field of the Invention
Embodiments of the present invention generally relate to plotting of implicit relations and more specifically relate to merging of polygons in adjacent tiles in plotting implicit inequalities.
Description of the Related Art
Plotting of implicit relations is a desirable feature in mathematical software packages. Given a function of two variables f(x,y), an implicit relation is denoted by ƒ(x,y) op 0, op ϵ{=, <, ≤, >, ≥}. If op ϵ{<, ≤, >, ≥}, then ƒ(x,y) op 0 is considered an implicit inequality; otherwise ƒ(x,y)=0 is considered an implicit equation. Plotting implicit relations on a two-dimensional Cartesian coordinate system differs from other plotting methods, since the plotting does not require the dependent variable, usually y, to be given explicitly in terms of the independent variable, usually x. Graphics algorithms for plotting implicit equations typically include two stages: detecting the contour of the function and rendering (plotting) the detected contour. When plotting implicit inequalities, the two stages are equivalent: detecting the region which satisfies the inequality and rendering the detected region. The boundary of the plotted region is often the contours of the function.
One well known approach to detecting the contour of a function of two variables recursively creates a rectangular mesh on top of the domain of the function. The recursion ends when a limit is reached in those parts of the graphing region on top of the domain of the function. The limit may be, for example, the size of a side of the smallest grid or the number of times to recur.
The recursive process begins with a rectangle of the size of the graphing region, i.e., the size of the display area for the plot, and recursively divides this rectangle into smaller and smaller rectangles until the limit is reached or some method, such as interval arithmetic, determines that no contour exists in the current rectangle. At the smallest rectangle, the function is evaluated at the corner of the smallest rectangle to determine whether or not a contour crosses a boundary of the rectangle. If the evaluation of the function at the corners suggests that the contour crosses the boundary of the curve, then the smallest rectangles (tiles) in the rectangular mesh may contain segments of the contour. Examples of this approach to detecting the contour of a function of two variables are described, for example, in K. G. Suffern, “Quadtree Algorithms for Contouring Functions of Two Variables,” The Computer Journal, Vol. 33, No. 5, pp. 402-407, 1990 (“Suffern” herein).
The approach of Suffern may be extended to implicit inequalities. Recursion is handled in the same way until the limit is reached or some method determines the contour of the function does not exist in the rectangle. If the recursion stops early, then the corners are evaluated to determine if the entire rectangle satisfies the inequality. If the recursion hits the limit, then, the smallest rectangles may contain segments of regions which satisfy the inequality.
The plotting stage involves creating graphical representations of the contour segments and/or regions. For an implicit equation, one approach is to draw lines in the smallest rectangle to represent the contour. For an implicit inequality, a polygon would be drawn with either at least one boundary lying on the edge of the rectangle or with the line estimate of the contour. If further analysis is needed on the graphical representations, such as tracing the contours, then connecting the lines or merging the polygons in adjacent rectangles (tiles) is needed. The merging/connecting is performed while backing out of the recursion. Depending on the function, the size of the graphing region, and the minimum rectangle size, there may be hundreds or thousands of polygons to be merged to plot the relation. Thus, the computational complexity of the merging process and the memory required for storing the polygons during the memory process may be important considerations, especially for devices with limited memory capacity and processing throughput.